package com.shm.leetcode;

import java.util.*;

/**
 * 347. 前 K 个高频元素
 * 给定一个非空的整数数组，返回其中出现频率前 k 高的元素。
 *
 *
 *
 * 示例 1:
 *
 * 输入: nums = [1,1,1,2,2,3], k = 2
 * 输出: [1,2]
 * 示例 2:
 *
 * 输入: nums = [1], k = 1
 * 输出: [1]
 *
 *
 * 提示：
 *
 * 你可以假设给定的 k 总是合理的，且 1 ≤ k ≤ 数组中不相同的元素的个数。
 * 你的算法的时间复杂度必须优于 O(n log n) , n 是数组的大小。
 * 题目数据保证答案唯一，换句话说，数组中前 k 个高频元素的集合是唯一的。
 * 你可以按任意顺序返回答案。
 * @author SHM
 */
public class TopKFrequent {
    /**
     * 方法一：堆
     * 思路与算法
     *
     * 首先遍历整个数组，并使用哈希表记录每个数字出现的次数，并形成一个「出现次数数组」。找出原数组的前 kk 个高频元素，就相当于找出「出现次数数组」的前 kk 大的值。
     *
     * 最简单的做法是给「出现次数数组」排序。但由于可能有 O(N)O(N) 个不同的出现次数（其中 NN 为原数组长度），故总的算法复杂度会达到 O(N\log N)O(NlogN)，不满足题目的要求。
     *
     * 在这里，我们可以利用堆的思想：建立一个小顶堆，然后遍历「出现次数数组」：
     *
     * 如果堆的元素个数小于 kk，就可以直接插入堆中。
     * 如果堆的元素个数等于 kk，则检查堆顶与当前出现次数的大小。如果堆顶更大，说明至少有 kk 个数字的出现次数比当前值大，故舍弃当前值；否则，就弹出堆顶，并将当前值插入堆中。
     * 遍历完成后，堆中的元素就代表了「出现次数数组」中前 kk 大的值。
     *
     * 复杂度分析
     *
     * 时间复杂度：O(N\log k)O(Nlogk)，其中 NN 为数组的长度。我们首先遍历原数组，并使用哈希表记录出现次数，每个元素需要 O(1)O(1) 的时间，共需 O(N)O(N) 的时间。随后，我们遍历「出现次数数组」，由于堆的大小至多为 kk，因此每次堆操作需要 O(\log k)O(logk) 的时间，共需 O(N\log k)O(Nlogk) 的时间。二者之和为 O(N\log k)O(Nlogk)。
     * 空间复杂度：O(N)O(N)。哈希表的大小为 O(N)O(N)，而堆的大小为 O(k)O(k)，共计为 O(N)O(N)。
     * 作者：LeetCode-Solution
     * 链接：https://leetcode-cn.com/problems/top-k-frequent-elements/solution/qian-k-ge-gao-pin-yuan-su-by-leetcode-solution/
     * @param nums
     * @param k
     * @return
     */
    public int[] topKFrequent(int[] nums, int k) {
        Map<Integer,Integer> map = new HashMap<>();

        for (int num : nums) {
//            if (map.containsKey(num)){
//                map.put(num,map.get(num)+1);
//            }else{
//                map.put(num,1);
//            }

            map.put(num,map.getOrDefault(num,0)+1);
        }
        PriorityQueue<int[]> priorityQueue = new PriorityQueue<>(new Comparator<int[]>() {
            @Override
            public int compare(int[] m, int[] n) {
                return m[1]-n[1];
            }
        });

        // int[] 的第一个元素代表数组的值，第二个元素代表了该值出现的次数
        for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
            int num = entry.getKey(),count = entry.getValue();
            if(priorityQueue.size()==k){
                if (priorityQueue.peek()[1]<count){
                    priorityQueue.poll();
                    priorityQueue.offer(new int[]{num,count});
                }
            }else{
                priorityQueue.offer(new int[]{num,count});
            }
        }

        //        作者：MisterBooo
        //        链接：https://leetcode-cn.com/problems/top-k-frequent-elements/solution/leetcode-di-347-hao-wen-ti-qian-k-ge-gao-pin-yuan-/
        // 遍历map，用最小堆保存频率最大的k个元素
        PriorityQueue<Integer> pq = new PriorityQueue<>(new Comparator<Integer>() {
            @Override
            public int compare(Integer a, Integer b) {
                return map.get(a) - map.get(b);
            }
        });
        for (Integer key : map.keySet()) {
            if (pq.size() < k) {
                pq.add(key);
            } else if (map.get(key) > map.get(pq.peek())) {
                pq.remove();
                pq.add(key);
            }
        }


        int[] res = new int[k];
        for (int i = 0; i < k; i++) {
            res[i] = priorityQueue.poll()[0];
        }
        return res;
    }

    /**
     * 解法三：桶排序法
     * 首先依旧使用哈希表统计频率，统计完成后，创建一个数组，将频率作为数组下标，对于出现频率不同的数字集合，存入对应的数组下标即可。
     * 复杂度分析
     * 时间复杂度：O(n)O(n)，nn 表示数组的长度。首先，遍历一遍数组统计元素的频率，这一系列操作的时间复杂度是 O(n)O(n)；桶的数量为 n + 1n+1，所以桶排序的时间复杂度为 O(n)O(n)；因此，总的时间复杂度是 O(n)O(n)。
     * 空间复杂度：很明显为 O(n)O(n)
     *
     * 作者：MisterBooo
     * 链接：https://leetcode-cn.com/problems/top-k-frequent-elements/solution/leetcode-di-347-hao-wen-ti-qian-k-ge-gao-pin-yuan-/
     * @param nums
     * @param k
     * @return
     */
    public int[] topKFrequent_2(int[] nums, int k) {
        Map<Integer, Integer> map = new HashMap<>();
        // 使用字典，统计每个元素出现的次数，元素为键，元素出现的次数为值
        for (int num : nums) {
            map.put(num, map.getOrDefault(num, 0) + 1);
        }

        //桶排序
        //将频率作为数组下标，对于出现频率不同的数字集合，存入对应的数组下标
        List<Integer>[] counts = new List[nums.length+1];
        for (Integer key : map.keySet()) {
            // 获取出现的次数作为下标
            Integer count = map.get(key);
            if (counts[count]==null){
                counts[count] = new ArrayList<>();
            }
            counts[count].add(key);
        }
        List<Integer> res = new ArrayList<>();
        // 倒序遍历数组获取出现顺序从大到小的排列
        for (int i = counts.length-1; i >=0 && res.size()<k; i--) {
            if(counts[i]==null){
                continue;
            }
            res.addAll(counts[i]);
        }
        int[] ans = new int[k];
        for (int i = 0; i < k; i++) {
            ans[i] = res.get(i);
        }
        return ans;
    }
}
